package org.moonshiner.alg.uf;

public class UFImpl implements UF {

	private int[] id;
	private int[] sz;
	private int count;
	
	public UFImpl(int n) {
		init(n);
	}
	
	@Override
	public void init(int n) {
		this.count = n;
		this.sz = new int[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}

	@Override
	public void union(int p, int q) {
		int i = find(p);
		int j = find(q);
		
		if(i == j){
			return;
		}
		
		if(sz[i] < sz[j]){
			id[i] = j;
			sz[j] += sz[i];
		}else{
			id[j] = i;
			sz[i] += sz[j];
		}
		
		count--;
		
	}

	@Override
	public int find(int p) {
		
		while(p != id[p]){
			p = id[p];
		}
		
		return p;
	}

	@Override
	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}

	@Override
	public int count() {
		return count;
	}

}
